package demo.practice.dp;

public class NumMatrix1 {


    //以下举证中 x只代表 占位， 字母代表 变量，或者顶点

    //[O,x,x]
    //[x,A,B]
    //[x,C,D]

    //构造一个二维前缀和如上图所示，要表示 矩形的面积
    //S(O,D)=S(O,C)+S(O,B)−S(O,A)+D


    //利用二维前序和 求 任意子矩阵的面积.
    //任意子矩阵都能看作一下图的一个模式图

    //[O,x,x,x]
    //[x,G,x,F]
    //[x,x,A,B]
    //[x,E,C,D]

    //S(A,D)=S(O,D)−S(O,E)−S(O,F)+S(O,G)
    //总结起来  ： 田字形，已知整体面积，上面面积，左边面积，左上面积，求右下角矩形的面积。 右下角矩形的面积=整体面积-上面面积-左边面积+左上面积


    //P304
    int[][] sum;

    public NumMatrix1(int[][] matrix) {

        //前缀和，矩阵如果整体多一列，可以做类似的操作
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return;

        sum = new int[matrix.length+1][matrix[0].length + 1];

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                sum[i+1][j + 1] = sum[i][j+1] + sum[i+1][j]+ matrix[i][j] - sum[i][j]  ;
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (sum == null)
            return 0;

        if(row1<0|| row2 >= sum.length || row1>row2)
            return 0;

        if(col1<0|| col2 >= sum[0].length-1 || col1>col2)
            return 0;

        //[O,x,x,x]
        //[x,G,x,F]
        //[x,x,A,B]
        //[x,E,C,D]
        //S(A,D)=S(O,D)−S(O,E)−S(O,F)+S(O,G)
       return sum[row2+1][col2+1]- sum[row2+1][col1]- sum[row1][col2+1]+ sum[row1][col1];
        //return sum[row2 + 1][col2 + 1] - sum[row2 + 1][col1] - this.sum[row1][col2 + 1] + this.sum[row1][col1];
    }



}
